/**
 * @Question.Title: 编辑距离
 * @Question.No: 72
 * @Author: DQ
 * @Date: 2021-01-24 14:08:34
 * @Description: 
 */
//给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 
//
// 你可以对一个单词进行如下三种操作： 
//
// 
// 插入一个字符 
// 删除一个字符 
// 替换一个字符 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：word1 = "horse", word2 = "ros"
//输出：3
//解释：
//horse -> rorse (将 'h' 替换为 'r')
//rorse -> rose (删除 'r')
//rose -> ros (删除 'e')
// 
//
// 示例 2： 
//
// 
//输入：word1 = "intention", word2 = "execution"
//输出：5
//解释：
//intention -> inention (删除 't')
//inention -> enention (将 'i' 替换为 'e')
//enention -> exention (将 'n' 替换为 'x')
//exention -> exection (将 'n' 替换为 'c')
//exection -> execution (插入 'u')
// 
//
// 
//
// 提示： 
//
// 
// 0 <= word1.length, word2.length <= 500 
// word1 和 word2 由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 1363 👎 0

package dq.leetcode.editor.cn;

import java.util.Arrays;

public class EditDistance {
    public static void main(String[] args) {
        Solution solution = new EditDistance().new Solution();
        System.out.println(solution.minDistance1("horse","ros"));
        System.out.println(solution.minDistance2("horse","ros"));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minDistance(String word1, String word2) {
        return minDistance2(word1,word2);
    }

    public int minDistance1(String word1, String word2) {
        if(word1.length()==0||word2.length()==0) return word2.length()+word1.length();
        //dp(i,j)表示 word1的前i个变换成Word2的前j个的编辑距离
        int[][] dp = new int[word1.length()][word2.length()];
        dp[0][0] = word1.charAt(0) == word2.charAt(0)?0:1;
        for (int i = 1; i < word1.length(); i++) {
            // 列，相等的话，删除前面多余的，不相等的话，用上一个并删除当前的字符
            dp[i][0] = word1.charAt(i) == word2.charAt(0)?i:dp[i-1][0]+1;
        }
        for (int j = 1; j < word2.length(); j++) {
            //行，相等话，插入前面没有的，不相等的话，用上一个并插入当前的
            dp[0][j] = word1.charAt(0) == word2.charAt(j)?j:dp[0][j-1]+1;
        }

        for (int i = 1; i < word1.length(); i++) {
            for (int j = 1; j < word2.length(); j++){
                if (word1.charAt(i)==word2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int insert = dp[i][j-1] + 1;
                    int delete = dp[i-1][j] + 1;
                    int replace = dp[i-1][j-1] + 1;
                    dp[i][j] = insert > delete ? delete : insert;
                    dp[i][j] = dp[i][j] > replace ? replace : dp[i][j];
                }
            }
        }
        System.out.println("  "+Arrays.toString(word2.toCharArray()));
        for (int i = 0; i < word1.length(); i++) {
            System.out.println(word1.charAt(i)+" " + Arrays.toString(dp[i]));
        }
        return dp[word1.length()-1][word2.length()-1];
    }

    //压缩状态
    public int minDistance2(String word1, String word2) {
        if(word1.length()==0||word2.length()==0) return word2.length()+word1.length();
        //dp(i,j)表示 word1的前i个变换成Word2的前j个的编辑距离
        int[] dp = new int[word2.length()];
        dp[0] = word1.charAt(0) == word2.charAt(0)?0:1;
        for (int j = 1; j < word2.length(); j++) {
            //行，相等话，插入前面没有的，不相等的话，用上一个并插入当前的
            dp[j] = word1.charAt(0) == word2.charAt(j)?j:dp[j-1]+1;
        }
        int[] pre = dp; //上一行
        int[] cur = new int[word2.length()]; //当前一行
        for (int i = 1; i < word1.length(); i++) {
            for (int j = 0; j < word2.length(); j++){
                if (word1.charAt(i)==word2.charAt(j)) {
                    cur[j] = j==0 ? i:(pre[j-1]);
                }else if(j==0){
                    cur[j] = pre[j] + 1;
                }else{
                    int insert = cur[j-1] + 1;
                    int delete = pre[j] + 1;
                    int replace = pre[j-1] + 1;
                    cur[j] = insert > delete ? delete : insert;
                    cur[j] = cur[j] > replace ? replace : cur[j];
                }
            }
            dp = cur;
            cur = pre;
            pre = dp;
        }

        return dp[word2.length()-1];
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}